package leetcode.doublepointer;

import java.util.Arrays;

//611. 有效三角形的个数
public class TriangleNumber {
    public static void main(String[] args) {
            int[] data = {2,2,3,4};
        System.out.println(triangleNumber2(data));
    }

    //排序加暴力搜索
    public static int triangleNumber1(int[] nums) {
        int count = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j=i-1;j>=0;j--){
                for (int k =j-1;k>=0;k--){
                    if (nums[k]+nums[j]>nums[i]){
                        count++;
                    }
                }
            }
        }
        return count;

    }
    //排序+双指针
    public static int triangleNumber2(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i =nums.length-1;i>=2;i--){
            int p = 0;
            int q = i-1;
            while (p<q){
                if (nums[p]+nums[q]>nums[i]){
                    count+=q-p;
                    q--;
                }else {
                    p++;
                }
            }
        }
        return count;

    }
}
